import com.sun.org.apache.bcel.internal.generic.FALOAD;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.List;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * User: 23735
 * Date: 2023-09-26
 * Time: 21:34
 */
public class Solution {

    /**
     * 预处理 + 哈希表 + 二分
     * 先用 map 记录每个字符对应出现的位置, 因为从前往后遍历, 所以字符出现的位置是递增的
     * 一个数组中的每个字符串都是要进行匹配的, 所以这是无法优化的, 所以在匹配时进行优化
     * 匹配每个字符串时, 子串的每个字符都要进行遍历, 但是该字符进行匹配时使用二分查找
     * 对该字符进行匹配时已经记录了上一个字符出现的位置
     * 所以匹配时使用二分查找找到第一个 > 前面字符出现的呃位置即可 (贪心)
     */
    public int numMatchingSubseq(String s, String[] words) {
        // map 记录了每个字符对应出现的位置, 因为从前往后遍历, 所以字符对应出现的位置是递增的
        HashMap<Character, List<Integer>> map = new HashMap<>();
        int len = s.length();
        for (int i = 0; i < len; i++) {
            List<Integer> list = map.getOrDefault(s.charAt(i), new ArrayList<>());
            list.add(i);
            map.put(s.charAt(i), list);
        }
        int ans = 0;
        for (String str: words) {
            int lastIndex = -1;
            boolean flag = true;
            // 针对每个字符串的每个字符使用二分查找
            for (int i = 0;i < str.length() && flag; i++) {
                char c = str.charAt(i);
                List<Integer> list = map.getOrDefault(c, null);
                if (list == null) {
                    flag = false;
                    break;
                }
                int left = 0;
                int right = list.size() - 1;
                // 二分查找
                while (left < right) {
                    int mid = ((right-left)>>1) + left;
                    if (list.get(mid) <= lastIndex) {
                        left = mid + 1;
                    } else {
                        right = mid;
                    }
                }
                if (list.get(left) > lastIndex) {
                    // 找到了
                    lastIndex = list.get(left);
                } else {
                    // 没找到
                    flag = false;
                }
            }
            if (flag) {
                ans++;
            }
        }
        return ans;
    }
}
